package 算法.NiuKe.JZ;

import 算法.NiuKe.ListNode;

/**
 * @author:谢君臣
 * @Date:2021/3/2019:40
 * @version:1.0
 * @function:
 * 输入两个单调递增的链表，输出两个链表合成后的链表，当然我们需要合成后的链表满足单调不减规则。
 * 示例1
 * 输入
 * {1,3,5},{2,4,6}
 * 返回值
 * {1,2,3,4,5,6}
 */
public class JZ16 {
    public static void main(String[] args) {

    }
    public static ListNode Merge(ListNode list1, ListNode list2) {
        if (list1==null)
            return list2;
        if (list2==null)
            return list1;
        ListNode p = list1;
        if (list1.val>list2.val){  // 保证list1的为小
            list1 = list2;
            list2 = p;
        }
        ListNode q = list1;
        p = q.next;
        while (list2!=null&&p!=null){
            ListNode temp = new ListNode(list2.val);
            list2 = list2.next;
            while (p!=null&&p.val<=temp.val) {p = p.next;q=q.next;}
            q.next = temp;
            temp.next = p;
            q = temp;
        }
        if (list2!=null){
            q.next = list2;
        }
        return list1;
    }
}
